package com.c2b.algorithm.newcoder.heapStackQueue;

import java.util.Stack;

/**
 * <a href="https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">包含min函数的栈</a>
 * <p>定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。</p>
 * <p>
 * 此栈包含的方法有：<br>
 * push(value):将value压入栈中<br>
 * pop():弹出栈顶元素<br>
 * top():获取栈顶元素<br>
 * min():获取栈中最小元素<br>
 * <p>
 * 数据范围：操作数量满足0≤n≤300  ，输入的元素满足∣val∣≤10000
 * 进阶：栈的各个操作的时间复杂度是O(1)  ，空间复杂度是O(n) </p>
 *
 * @author c2b
 * @since 2023/3/14 15:21
 */
public class BM0043StackContainingMinFunction_S {
    /**
     * 正常栈
     */
    Stack<Integer> stack = new Stack<>();
    /**
     * 最小值栈
     */
    Stack<Integer> minStack = new Stack<>();

    public void push(int val) {
        stack.push(val);
        if (minStack.empty()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek() <= val ? minStack.peek() : val);
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}
